package arithmetic.leetCode;

import arithmetic.geektime.tree.TreeNode;
import arithmetic.geektime.tree.TreeTraverse;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author dycong
 * @date 2019/11/21 9:16
 */
public class TreePostorderTraversal_145 {

    public static void main(String[] args) {
        TreeTraverse.TreeHelper treeHelper = new TreeTraverse.TreeHelper();
        TreeNode root = treeHelper.getTree(5);

        TreePostorderTraversal_145 twoSum_1 = new TreePostorderTraversal_145();

        System.out.println(twoSum_1.postorderTraversal(root));
        System.out.println(twoSum_1.postorderTraversal_2(root));
        System.out.println(twoSum_1.postorderTraversal_3(root));
    }

    /**
     * 前序遍历是：root - left - right, 后序遍历：left - right - root,则翻转一下 left 与 right ，最后结果 reverse 即可
     * 注意栈性质，先入后出
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        if (null == root) {
            return Collections.emptyList();
        }
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ret.add(node.val);

            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(ret);
        return ret;
    }

    /**
     * 递归 1 比较慢
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal_2(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<Integer> ret = new ArrayList<>();
        ret.addAll(postorderTraversal_2(root.left));
        ret.addAll(postorderTraversal_2(root.right));
        ret.add(root.val);
        return ret;
    }

    /**
     * 递归 1 很快
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal_3(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<Integer> ret = new ArrayList<>();
        return postOrder(root, ret);
    }

    private List<Integer> postOrder(TreeNode root, List<Integer> ret) {
        if (root == null) return ret;
        postOrder(root.left, ret);
        postOrder(root.right, ret);
        ret.add(root.val);
        return ret;
    }
}
